/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
 var serialize = function(root) {
    if(!root){
        return new Array();
    }
    let stack=Array.of(root);
    let ret=new Array(),nc=0;
    while(stack.length!==0&&nc!=stack.length){
        let node=stack.shift();
        if(node){
            ret.push(node.val);
            stack.push(node.left);
            nc+=node.left ? 0:1;
            stack.push(node.right);
            nc+=node.right ? 0:1;
        }
        else{
            ret.push(null);
            nc--;
        }  
    }
    return ret;
};

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
var deserialize = function(data) {
    if(data.length==0){
        return null;
    }
    let i=1;
    let root=new TreeNode(data[0])
    let layer=Array.of(root);
    while(i<data.length){
        let temp=new Array();
        for(let n of layer){
            if(i>=data.length){
                return root;
            }
            if(data[i]||data[i]===0){
                n.left=new TreeNode(data[i]);
                temp.push(n.left);
            }
            i++;
            if(data[i]||data[i]===0){
                n.right=new TreeNode(data[i]);
                temp.push(n.right);
            }
            i++;
        }
        layer=temp;
    }
    return root;


};

/**
 * Your functions will be called as such:
 * deserialize(serialize(root));
 */


//  执行用时：
//  132 ms
//  , 在所有 JavaScript 提交中击败了
//  96.72%
//  的用户
//  内存消耗：
//  49.2 MB
//  , 在所有 JavaScript 提交中击败了
//  21.55%
//  的用户